﻿// 快排及topk问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

int partation(int arr[], int f, int l,bool falg = false)
{
    /*
    * 以第一个数为基准数，记录基准数，用i，j分别记录数组开始和末尾的下标
    * 从后往前找第一个小于基准数的元素，将其放在i所在的位置，i++
    * 从i开始找第一个大于基准数的值，将其放在j所在的位置，j--；
    * 重复上面的操作，直至i=j，将第一个数放在i所在的位置
    */
    int val = arr[f];
    while (f < l)
    {
        if (!falg)
        {
            while (f < l && arr[l] >= val)
                l--;
            if (f < l)
            {
                arr[f] = arr[l];
                f++;
            }
            while (f < l && arr[f] < val)
                f++;
            if (f < l)
            {
                arr[l] = arr[f];
                l--;
            }
        }
        else
        {
            while (f < l && arr[l] <=val)
                l--;
            if (f < l)
            {
                arr[f] = arr[l];
                f++;
            }
            while (f < l && arr[f] > val)
                f++;
            if (f < l)
            {
                arr[l] = arr[f];
                l--;
            }
        }       
        
    }
    arr[f] = val;
    return f;
}

void quicksort2(int arr[], int i, int j)
{
    if (i < j)
    {
        int m = partation(arr, i, j,true);
        quicksort2(arr, i, m - 1);
        quicksort2(arr, m + 1, j);
    }
}
void quicksort(int arr[], int size)
{
    quicksort2(arr, 0, size - 1);

}

void TopKSort1(int arr[], int f, int l, int k)
{
    if (f < l)
    {
        int pos = partation(arr, f, l, false);
        if (pos == k - 1)
            return;
        else if (pos < k - 1)
            return TopKSort1(arr, pos + 1, l, k);
        else
            return TopKSort1(arr, f, pos - 1, k);
    }
}
void TopKSortS(int arr[], int size, int k)
{
    TopKSort1(arr, 0, size - 1, k);
}
//最大的k个值
void TopKSort2(int arr[], int f, int l, int k)
{
    if (f < l)
    {
        int pos = partation(arr, f, l, true);
        if (pos == k - 1)
            return;
        else if (pos < k - 1)
            return TopKSort2(arr, pos + 1, l, k);
        else
            return TopKSort2(arr, f, pos - 1, k);
    }
}
void TopKSortM(int arr[], int size, int k)
{
    TopKSort2(arr, 0, size - 1, k);
}
//最小的k个值
int main()
{
    srand(time(0));
    int arr[15];
    for (int i = 0; i < 15; i++)
    {
        arr[i] = rand() % 100;
        cout << arr[i] << " ";
    }
    cout << endl;
    quicksort(arr, 15);
    for (int i = 0; i < 15; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;


    TopKSortM(arr, 15, 5);
    for (int i = 0; i < 5; i++)
    {        
        cout << arr[i] << " ";
    }
    cout << endl;


    TopKSortS(arr, 15, 5);
    for (int i = 0; i < 5; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

}


